// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.algorithms;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeMap;

import com.thalesgroup.graphFramework.core.Edge;
import com.thalesgroup.graphFramework.core.Graph;

import com.thalesgroup.graphFramework.measure.Measure;

@SuppressWarnings("unused")
public class FloydWarshall {
	public static <V, E> AdMatrix compute(final Graph<V, E> g,
			final Measure<E> measure) {

		AdMatrix old;
		AdMatrix current;

		final int size = g.getVerticesSize();
		old = new AdMatrix1(size);
		current = new AdMatrix1(size);

		for(Iterator<Edge<V,E>> ie=g.getEdges(); ie.hasNext();) {
			Edge<V,E> e=ie.next();
			final double val = measure.eval(e.getEdge());
			old.set(e.getIn().getIndex(), e.getOut().getIndex(), val);
		}

		if (current.get(0, 1) == 1) {
			throw new RuntimeException();
		}

		for (int k = 0; k < size; k++) {
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					final double ij = old.get(i, j);
					final double ik = old.get(i, k);
					final double kj = old.get(k, j);
					final double nValue = Math.min(ij, ik + kj);
					current.set(i, j, nValue);

				}
			}

			final AdMatrix tmp = old;
			old = current;
			current = tmp;
		}

		return old;
	}

	public static interface AdMatrix {
		public int size();

		public void set(int i, int j, double v);

		public double get(int i, int j);
	}

	private static final class AdMatrix4 implements AdMatrix {

		final private HashMap<Integer, HashMap<Integer, Double>> data;
		final private int size;

		public AdMatrix4(final int size) {
			data = new HashMap<Integer, HashMap<Integer, Double>>();
			this.size = size;
		}

		public double get(final int i, final int j) {
			final HashMap<Integer, Double> line = data.get(i);
			if (line != null) {
				final Double v = line.get(j);
				return (v != null) ? v : Double.MAX_VALUE;
			} else {
				return Double.MAX_VALUE;
			}
		}

		public void set(final int i, final int j, final double v) {
			HashMap<Integer, Double> line = data.get(i);
			if (line == null) {
				line = new HashMap<Integer, Double>();
				data.put(i, line);
			}

			line.put(j, v);
		}

		public int size() {
			return size;
		}

	}

	private static final class AdMatrix0 implements AdMatrix {
		final private HashMap<Integer, Double>[] data;

		final public int size() {
			return data.length;
		}

		@SuppressWarnings("unchecked")
		public AdMatrix0(final int size) {
			data = new HashMap[size];
		}

		final public double get(final int i, final int j) {
			final HashMap<Integer, Double> l = data[i];
			// final double result;

			if (l == null) {
				return Double.MAX_VALUE;
			} else {
				final Double v = l.get(j);
				return (v == null) ? Double.MAX_VALUE : v;
			}
		}

		final public void set(final int i, final int j, final double v) {
			HashMap<Integer, Double> l = data[i];
			if (l == null) {
				l = new HashMap<Integer, Double>();
				data[i] = l;
			}

			l.put(j, v);
		}
	}

	private static final class AdMatrix1 implements AdMatrix {
		final public Vector1[] lines;

		public AdMatrix1(final int size) {
			lines = new Vector1[size];
		}

		final public double get(final int i, final int j) {
			final Vector1 l = lines[i];
			return (l == null) ? Double.MAX_VALUE : l.get(j);
		}

		final public void set(final int i, final int j, final double v) {
			Vector1 l = lines[i];
			if (l == null) {
				l = new Vector1();
				lines[i] = l;
			}
			l.set(j, v);
		}

		public int size() {
			return lines.length;
		}

	}

	private static final class Vector1 {

		private final HashMap<Integer, Double> data = new HashMap<Integer, Double>();

		final public void set(final int j, final double v) {
			data.put(j, v);
		}

		final public double get(final int j) {
			final Double v = data.get(j);
			return (v == null) ? Double.MAX_VALUE : v;
		}

	}

	private static final class AdMatrix2 implements AdMatrix {
		final private TreeMap<Integer, Double>[] lines;
		final private int size;

		public int size() {
			return size;
		}

		@SuppressWarnings("unchecked")
		public AdMatrix2(final int size) {
			this.size = size;
			lines = new TreeMap[size];
		}

		public void set(final int i, final int j, final double v) {
			if (lines[i] == null) {
				lines[i] = new TreeMap<Integer, Double>();
			}

			lines[i].put(j, v);
		}

		public double get(final int i, final int j) {
			if (lines[i] != null) {
				final Double v = lines[i].get(j);
				return (v == null) ? Double.MAX_VALUE : v;
			} else {
				return Double.MAX_VALUE;
			}
		}
	}

	private static final class AdMatrix3 implements AdMatrix {
		private final Vector[] lines;
		private final int size;

		public int size() {
			return size;
		}

		public AdMatrix3(final int size) {
			this.size = size;
			lines = new Vector[size];
		}

		public void set(final int i, final int j, final double v) {
			if (lines[i] == null) {
				lines[i] = new Vector();
			}

			lines[i].set(j, v);
		}

		public double get(final int i, final int j) {
			return (lines[i] == null) ? Double.MAX_VALUE : lines[i].get(j);
		}
	}

	private static final class Vector {
		private double[] data = new double[0];
		private int[] index = new int[0];

		public void set(final int i, final double v) {
			int pos = Arrays.binarySearch(index, i);
			if (pos >= 0) {
				data[pos] = v;
			} else {
				pos = -(pos + 1);
				final int size = data.length;
				final double[] nData = new double[size + 1];
				final int[] nIndex = new int[size + 1];

				if (pos > 0) {
					System.arraycopy(data, 0, nData, 0, pos);
				}
				if (pos - size - 1 > 0) {
					System.arraycopy(data, pos + 1, nData, pos + 2, pos - size
							- 1);
				}

				if (pos > 0) {
					System.arraycopy(index, 0, nIndex, 0, pos);
				}
				if (pos - size - 1 > 0) {
					System.arraycopy(index, pos + 1, nIndex, pos + 2, pos
							- size - 1);
				}

				nData[pos] = v;
				nIndex[pos] = i;

				data = nData;
				index = nIndex;
			}
		}

		public double get(final int i) {
			final int pos = Arrays.binarySearch(index, i);
			return (pos >= 0) ? data[pos] : Double.MAX_VALUE;
		}
	}
}
